package main

import "fmt"

// 找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
//
//示例 1:
//
//输入: k = 3, n = 7
//输出: [[1,2,4]]
//示例 2:
//
//输入: k = 3, n = 9
//输出: [[1,2,6], [1,3,5], [2,3,4]]
func main() {
	sum3 := combinationSum3(3, 9)
	fmt.Println(sum3)
}

func combinationSum3(k int, n int) (ans [][]int) {
	var temp []int
	var dfs func(cur, rest int)
	dfs = func(cur, rest int) {
		// 找到一个答案
		if len(temp) == k && rest == 0 {
			ans = append(ans, append([]int(nil), temp...))
			return
		}
		if len(temp) == k && rest > 0 { //万一选了k个数了，却还是凑不到总和n
			return
		}
		for i := cur; i < 10; i++ {
			if rest-i < 0 { //如果当前数字加起来超过了总和n，当前数字以后的数字都不用看了
				break
			}
			// 选当前数字
			temp = append(temp, i)
			dfs(i+1, rest-i) //向下递归选择i+1而不是cur+1是因为组合中不允许重复数字
			temp = temp[:len(temp)-1]
		}

	}
	dfs(1, n)
	return

}
